﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace 修为尽失.辅助.exts
{
    public static class Sort
    {
        /// <summary>
        /// 双向冒泡排序
        /// Worst case performance: 	O(n2)
        /// Best case performance: 	O(n)
        /// Average case performance: 	O(n2)
        /// Worst case space complexity: 	O(1) auxiliary
        /// </summary>
        /// <param name="arrayToSort"></param>
        /// <returns></returns>
        public static IList BiDerectionalBubleSort(this IList arrayToSort)
        {
            var limit = arrayToSort.Count;
            var st = -1;
            var swapped = false;
            do
            {
                swapped = false;
                st++;
                limit--;
                for (var j = st; j < limit; j++)
                    if (((IComparable) arrayToSort[j]).CompareTo(arrayToSort[j + 1]) > 0)
                    {
                        var temp = arrayToSort[j];
                        arrayToSort[j] = arrayToSort[j + 1];
                        arrayToSort[j                  + 1] = temp;
                        swapped = true;
                    }

                for (var j = limit - 1; j >= st; j--)
                    if (((IComparable) arrayToSort[j]).CompareTo(arrayToSort[j + 1]) > 0)
                    {
                        var temp = arrayToSort[j];
                        arrayToSort[j] = arrayToSort[j + 1];
                        arrayToSort[j                  + 1] = temp;
                        swapped = true;
                    }
            } while (st < limit && swapped);

            return arrayToSort;
        }

        /// <summary>
        ///冒泡排序
        ///最差性能: 	O(n2)
        ///最佳性能: 	O(n)
        ///平均性能: 	O(n2)
        ///糟糕时空间复杂性: 	O(1) 备用
        /// </summary>
        /// <param name="arrayToSort"></param>
        /// <returns></returns>
        public static IList BubbleSort(this IList arrayToSort)
        {
            var n = arrayToSort.Count - 1;
            for (var i = 0; i < n; i++)
            for (var j = n; j > i; j--)
                if (((IComparable) arrayToSort[j - 1]).CompareTo(arrayToSort[j]) > 0)
                {
                    var temp = arrayToSort[j - 1];
                    arrayToSort[j - 1] = arrayToSort[j];
                    arrayToSort[j] = temp;
                }

            return arrayToSort;
        }

        public static IList MergeSort(this IList a, int low, int height)
        {
            var l = low;
            var h = height;
            if (l >= h)
                return a;
            var mid = (l + h) / 2;
            MergeSort(a, l, mid);
            MergeSort(a, mid + 1, h);
            var end_lo = mid;
            var start_hi = mid + 1;
            while (l <= end_lo && start_hi <= h)
                if (((IComparable) a[l]).CompareTo(a[start_hi]) < 0)
                {
                    l++;
                }
                else
                {
                    var temp = a[start_hi];
                    for (var k = start_hi - 1; k >= l; k--) a[k + 1] = a[k];
                    a[l] = temp;
                    l++;
                    end_lo++;
                    start_hi++;
                }

            return a;
        }

        /// <summary>
        /// 冒泡排序
        /// </summary>
        /// <param name="arry">要排序的整数数组</param>
        public static void BubbleSort(this int[] arry)
        {
            for (int i = 0; i < arry.Length; i++)
            {
                for (int j = 0; j < arry.Length - 1 - i; j++)
                {
                    //比较相邻的两个元素，如果前面的比后面的大，则交换位置
                    if (arry[j] > arry[j + 1])
                    {
                        int temp = arry[j + 1];
                        arry[j + 1] = arry[j];
                        arry[j] = temp;
                    }
                }
            }
        }

        /// <summary>
        /// 快速排序
        /// </summary>
        /// <param name="arry">要排序的数组</param>
        /// <param name="left">低位</param>
        /// <param name="right">高位</param>
        public static void QuickSort(this int[] arry, int left, int right)
        {
            //左边索引小于右边，则还未排序完成 　　
            if (left < right)
            {
                //取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移 　　
                int middle = arry[(left + right) / 2];
                int i = left  - 1;
                int j = right + 1;
                while (true)
                {
                    //移动下标，左边的往右移动，右边的向左移动
                    while (arry[++i] < middle && i < right)
                        ;
                    while (arry[--j] > middle && j > 0)
                        ;
                    if (i >= j)
                        break;
                    //交换位置
                    int number = arry[i];
                    arry[i] = arry[j];
                    arry[j] = number;
                }

                QuickSort(arry, left, i - 1);
                QuickSort(arry, j       + 1, right);
            }
        }

        /// <summary>
        /// 直接插入排序
        /// </summary>
        /// <param name="arry">要排序的数组</param>
        public static void InsertSort(this int[] arry)
        {
            //直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的
            for (int i = 1; i < arry.Length; i++)
            {
                //如果当前元素小于其前面的元素
                if (arry[i] < arry[i - 1])
                {
                    //用一个变量来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 
                    int temp = arry[i];
                    int j = 0;
                    for (j = i - 1; j >= 0 && temp < arry[j]; j--)
                    {
                        arry[j + 1] = arry[j];
                    }

                    arry[j + 1] = temp;
                }
            }
        }

        /// <summary>
        /// 希尔排序
        /// </summary>
        /// <param name="arry">待排序的数组</param>
        public static void ShellSort(this int[] arry)
        {
            int length = arry.Length;
            for (int h = length / 2; h > 0; h = h / 2)
            {
                //here is insert sort
                for (int i = h; i < length; i++)
                {
                    int temp = arry[i];
                    if (temp < arry[i - h])
                    {
                        for (int j = 0; j < i; j += h)
                        {
                            if (temp < arry[j])
                            {
                                temp = arry[j];
                                arry[j] = arry[i];
                                arry[i] = temp;
                            }
                        }
                    }
                }
            }
        }

        /// <summary>
        /// 简单选择排序
        /// </summary>
        /// <param name="arry">待排序的数组</param>
        public static void SimpleSelectSort(this int[] arry)
        {
            int tmp = 0;
            int t = 0; //最小数标记
            for (int i = 0; i < arry.Length; i++)
            {
                t = i;
                for (int j = i + 1; j < arry.Length; j++)
                {
                    if (arry[t] > arry[j])
                    {
                        t = j;
                    }
                }

                tmp = arry[i];
                arry[i] = arry[t];
                arry[t] = tmp;
            }
        }

        /// <summary>
        /// 堆排序
        /// </summary>
        /// <param name="arry"></param>
        public static void HeapSort(this int[] arry, int top)
        {
            List<int> topNode = new List<int>();
            for (int i = arry.Length / 2 - 1; i >= 0; i--)
            {
                HeapAdjust(arry, i, arry.Length);
            }

            for (int i = arry.Length - 1; i >= arry.Length - top; i--)
            {
                int temp = arry[0];
                arry[0] = arry[i];
                arry[i] = temp;
                HeapAdjust(arry, 0, i);
            }
        }

        /// <summary>
        /// 构建堆
        /// </summary>
        /// <param name="arry"></param>
        /// <param name="parent"></param>
        /// <param name="length"></param>
        private static void HeapAdjust(int[] arry, int parent, int length)
        {
            int temp = arry[parent];
            int child = 2 * parent + 1;
            while (child < length)
            {
                if (child + 1 < length && arry[child] < arry[child + 1])
                    child++;
                if (temp >= arry[child])
                    break;
                arry[parent] = arry[child];
                parent = child;
                child = 2 * parent + 1;
            }

            arry[parent] = temp;
        }

        /// <summary>
        /// 归并排序
        /// </summary>
        /// <param name="arry"></param>
        /// <param name="first"></param>
        /// <param name="last"></param>
        public static void MergeSort(this int[] arry, int first, int last)
        {
            if (first + 1 < last)
            {
                int mid = (first + last) / 2;
                MergeSort(arry, first, mid);
                MergeSort(arry, mid, last);
                Merger(arry, first, mid, last);
            }
        }

        /// <summary>
        /// 归并
        /// </summary>
        /// <param name="arry"></param>
        /// <param name="first"></param>
        /// <param name="mid"></param>
        /// <param name="last"></param>
        private static void Merger(int[] arry, int first, int mid, int last)
        {
            Queue<int> tempV = new Queue<int>();
            int indexA, indexB;
            //设置indexA，并扫描subArray1 [first,mid]
            //设置indexB,并扫描subArray2 [mid,last]
            indexA = first;
            indexB = mid;
            //在没有比较完两个子标的情况下，比较 v[indexA]和v[indexB]
            //将其中小的放到临时变量tempV中
            while (indexA < mid && indexB < last)
            {
                if (arry[indexA] < arry[indexB])
                {
                    tempV.Enqueue(arry[indexA]);
                    indexA++;
                }
                else
                {
                    tempV.Enqueue(arry[indexB]);
                    indexB++;
                }
            }

            //复制没有比较完子表中的元素
            while (indexA < mid)
            {
                tempV.Enqueue(arry[indexA]);
                indexA++;
            }

            while (indexB < last)
            {
                tempV.Enqueue(arry[indexB]);
                indexB++;
            }

            int index = 0;
            while (tempV.Count > 0)
            {
                arry[first + index] = tempV.Dequeue();
                index++;
            }
        }

        /// <summary>
        /// 基数排序
        /// 约定:待排数字中没有0,如果某桶内数字为0则表示该桶未被使用,输出时跳过即可
        /// </summary>
        /// <param name="arry">待排数组 /* 最大数字不超过999999999...(array_x个9) */</param>
        /// <param name="array_x">桶数组第一维长度</param>
        /// <param name="array_y">桶数组第二维长度</param>
        public static void RadixSort(this int[] arry, int array_x = 10, int array_y = 100)
        {
            for (int i = 0; i < array_x; i++)
            {
                int[,] bucket = new int[array_x, array_y];
                foreach (var item in arry)
                {
                    int temp = (item / (int) Math.Pow(10, i)) % 10;
                    for (int l = 0; l < array_y; l++)
                    {
                        if (bucket[temp, l] == 0)
                        {
                            bucket[temp, l] = item;
                            break;
                        }
                    }
                }

                for (int o = 0, x = 0; x < array_x; x++)
                {
                    for (int y = 0; y < array_y; y++)
                    {
                        if (bucket[x, y] == 0)
                            continue;
                        arry[o++] = bucket[x, y];
                    }
                }
            }
        }
    }
}